package org.example.myleet.rosalind.cntq;

import org.example.myleet.rosalind.chbp.Solution;
import org.example.myleet.rosalind.utils.NewickTreeNode;
import org.example.myleet.rosalind.utils.NewickTreeUtil;
import org.example.myleet.rosalind.utils.Quartet;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class SolutionClumsy {
    public static void main(String[] args) throws IOException {
        Solution solution = new Solution();
        String path = solution.getClass().getResource("").getPath() + "example.txt";
        try (BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(path)))) {
            String line = br.readLine();
            int n = Integer.parseInt(line.trim());
            String newick = br.readLine().trim();
            NewickTreeNode root = NewickTreeUtil.parse(null, newick);
            Set<String> allTaxa = findAllTaxaUnderCurNode(root);
            //try all splits by BFS
            Set<Quartet> allQuartets = new HashSet<>();
            Queue<NewickTreeNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) {
                int size = queue.size();
                for (int i = 0; i < size; ++i) {
                    NewickTreeNode node = queue.poll();
                    for (NewickTreeNode child : node.getChildren()) {
                        queue.offer(child);
                    }
                    Set<String> taxaSet = findAllTaxaUnderCurNode(node);
                    if (taxaSet.size() < 2) {
                        continue;
                    }
                    Set<String> complementaryTaxaSet = new HashSet<>(allTaxa);
                    complementaryTaxaSet.removeAll(taxaSet);
                    if (complementaryTaxaSet.size() < 2) {
                        continue;
                    }
                    List<String> taxaList = new ArrayList<>(taxaSet);
                    List<String> complementaryTaxaList = new ArrayList<>(complementaryTaxaSet);
                    String a, b, c, d;
                    for (int w = 0; w < taxaList.size(); ++w) {
                        a = taxaList.get(w);
                        for (int x = w + 1; x < taxaList.size(); ++x) {
                            b = taxaList.get(x);
                            for (int y = 0; y < complementaryTaxaList.size(); ++y) {
                                c = complementaryTaxaList.get(y);
                                for (int z = y + 1; z < complementaryTaxaList.size(); ++z) {
                                    d = complementaryTaxaList.get(z);
                                    Quartet quartet = new Quartet(a, b, c, d);
                                    allQuartets.add(quartet);
                                }
                            }
                        }
                    }
                }
            }
            System.out.println(allQuartets.size());
        }
    }

    private static Set<String> findAllTaxaUnderCurNode(NewickTreeNode cur) {
        Set<String> taxaSet = new HashSet<>();
        Queue<NewickTreeNode> queue = new LinkedList<>();
        queue.offer(cur);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                NewickTreeNode node = queue.poll();
                if (node.getValue().length() > 0) {
                    taxaSet.add(node.getValue());
                }
                for (NewickTreeNode child : node.getChildren()) {
                    queue.offer(child);
                }
            }
        }
        return taxaSet;
    }
}
